package com.cat.greedyAlgorithm;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/course-schedule-iii/
 * @create 2025/8/26 09:46
 * @since JDK17
 */

public class Solution39 {
    public int scheduleCourse(int[][] courses) {
        int time = 0;
        Arrays.sort(courses, (o1, o2) -> o1[1] - o2[1]);
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        for (var c : courses) {
            if (time + c[0] <= c[1]) {
                time += c[0];
                heap.add(c[0]);
            } else {
                if (!heap.isEmpty() && heap.peek() > c[0]) {
                    time += c[0] - heap.poll();
                    heap.add(c[0]);
                }
            }
        }
        return heap.size();
    }
}
